from queue import Queue


class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def create_binary_tree(input_list=[]):
    '''
    构建二叉树
    :param input_list: 输入数列
    :return:
    '''
    if input_list is None or len(input_list) == 0:
        return None
    data = input_list.pop(0)
    if data is None:
        return None
    node = TreeNode(data)
    node.left = create_binary_tree(input_list)
    node.right = create_binary_tree(input_list)
    return node


def pre_order_traversal(node):
    '''
    前序遍历
    :param node: 二叉树节点
    :return:
    '''
    if node is None:
        return
    print(node.data)
    pre_order_traversal(node.left)
    pre_order_traversal(node.right)
    return node


def in_order_traversal(node):
    '''
    中序遍历
    :param node: 二叉树节点
    :return:
    '''
    if node is None:
        return
    in_order_traversal(node.left)
    print(node.data)
    in_order_traversal(node.right)
    return node


def post_order_traversal(node):
    '''
    后序遍历
    :param node: 二叉树节点
    :return:
    '''
    if node is None:
        return
    post_order_traversal(node.left)
    post_order_traversal(node.right)
    print(node.data)
    return node


def level_order_traversal(node):
    queue = Queue()
    queue.put(node)
    while not queue.empty():
        node = queue.get()
        print(node.data)
        if node.left is not None:
            queue.put(node.left)
        if node.right is not None:
            queue.put(node.right)


def up_adjust(array=[]):
    '''
    二叉堆尾结点上浮操作
    :param array:  原数组
    :return:
    '''
    child_index = len(array) - 1
    parent_index = (child_index - 1) // 2
    # temp 保存插入的叶子节点值，用于最后的赋值
    temp = array[child_index]
    while child_index > 0 and temp < array[parent_index]:
        array[child_index] = array[parent_index]
        child_index = parent_index
        parent_index = (parent_index - 1) // 2
    array[child_index] = temp



def down_adjust(parent_index, length, array=[]):
    '''
    二叉堆的节点下沉操作
    :param parent_index:待下沉的节点下标
    :param length: 堆的长度范围
    :param array: 原数组
    :return:
    '''
    # temp 保存父节点值，用于最后的赋值
    temp = array[parent_index]
    child_index = 2 * parent_index + 1
    while child_index < length:
        # 如果有右孩子，且右孩子的值小于左孩子的值，则定位到右孩子
        if child_index + 1 < length and array[child_index + 1] < array[child_index]:
            child_index += 1
        if temp <= array[child_index]:
            break
        array[parent_index] = array[child_index]
        parent_index = child_index
        child_index = 2 * child_index + 1
    array[parent_index] = temp


def build_heap(array=[]):
    '''
    二叉堆的构建操作
    :param array: 原数组
    :return:
    '''
    for i in range((len(array) - 2) // 2, -1, -1):
        down_adjust(i, len(array), array)


if __name__ == '__main__':
    my_input_list = list([3, 2, 9, None, None, 10, None, None, 8, None, 4])
    root = create_binary_tree(my_input_list)
    print('前序遍历:')
    pre_order_traversal(root)
    print('中序遍历:')
    in_order_traversal(root)
    print('后序遍历:')
    post_order_traversal(root)

    print('层级排序:')
    level_order_traversal(root)
    my_array = list([1, 3, 4, 6, 5, 7, 8, 9, 10, 0])
    up_adjust(my_array)
    print(my_array)
    my_array = list([7, 1, 3, 10, 5, 2, 8, 9, 6])
    build_heap(my_array)
    print(my_array)
